In data traffic management it is known to implement a WFQ scheme to achieve fair scheduling of multiple queues at a network interface. An example of a WFQ scheduler implementing eight classes of service is illustrated in FIG. 1. The WFQ scheduler is used to schedule servicing of queues having classes of service CoS3 to CoS7. Classes of services CoS0 to CoS2 have been assigned a high priority rating and are typically serviced using one or more servicing algorithms such as an exhaustive round robin scheme.
In FIG. 1 classes of service CoS3 to CoS7 are serviced using the WFQ scheme wherein each CoS has assigned thereto a service weight which is factored into the servicing scheme.
In general, WFQ is an algorithm used to select a queue amongst a multitude of queues for servicing at any point in time. Each queue on a WFQ structure is assigned a weight and the effect of service provided to a queue is the proportion of the queue's weight divided by the sum of all of the queues' weights.
The present invention is particularly directed to WFQ implementations for use on very high speed interfaces in order to deal with the constraints of the implementing devices which may be, for example, network processors, field programmable gate arrays (FPGA) and applications specific integrated circuits (ASIC). Typical of the constraints of implementing devices are the number of processing cycles any single packet may consume within the devices, and the latency associated with accessing a packet's context. Such constraints make it difficult to impossible to use theoretically ideal WFQ algorithms. Furthermore, if special care is not taken with the optimizations necessary for WFQ implementations, parasitic second order effects such as service jitter can become problematic, potentially resulting in down stream service level agreement (SLA) violations.
In the present application jitter can be defined as the variance in time between when a queue should have theoretically been selected for service and the actual time the queue has been selected. The goal of the WFQ algorithm of the present application is to address the performance constraints on very high speed interfaces while maintaining control of the jitter characteristics of the algorithm.
Weighted fair queuing schemes are well known and are described extensively in the prior art. None of the prior art, of which Applicants are aware, account for the performance constraints associated with network processors nor do any prior art implementations deal with maintaining bounds on jitter characteristics as jitter is non-existent with an ideal implementation of a WFQ.
Accordingly, there is a present requirement, which requirement will become even more desirable in the future, to reduce or eliminate service jitter in implementations involving very high speeds.